package algothrim

import (
	"container/list"
)

// LRUCache is a struct for LRU cache
type LRUCache struct {
	capacity int
	cache    map[int]*list.Element
	list     *list.List
}

// Pair is a struct for key and value
type Pair struct {
	key   int
	value int
}

// Constructor is a function to create a new LRU cache
func Constructor(capacity int) LRUCache {
	return LRUCache{
		capacity: capacity,
		cache:    make(map[int]*list.Element),
		list:     list.New(),
	}
}

// Get is a function to get the value of a key
func (lru *LRUCache) Get(key int) int {
	if element, ok := lru.cache[key]; ok {
		lru.list.MoveToFront(element)
		return element.Value.(Pair).value
	}
	return -1
}

// Put is a function to put a key and value into the cache
func (lru *LRUCache) Put(key int, value int) {
	if element, ok := lru.cache[key]; ok {
		lru.list.MoveToFront(element)
		element.Value = Pair{key: key, value: value}
	} else {
		if lru.list.Len() >= lru.capacity {
			delete(lru.cache, lru.list.Back().Value.(Pair).key)
			lru.list.Remove(lru.list.Back())
		}
		lru.list.PushFront(Pair{key: key, value: value})
		lru.cache[key] = lru.list.Front()
	}
}

type LRUCacheI struct {
	Capacity int
	Cache    map[int]*list.Element
	List     list.List
}

func (lru *LRUCacheI) Put(key int, value int) {
	if element, ok := lru.Cache[key]; ok {
		lru.List.MoveToFront(element)
		element.Value = Pair{key: key, value: value}
	} else {
		if lru.List.Len() >= lru.Capacity {
			delete(lru.Cache, lru.List.Back().Value.(Pair).key)
			lru.List.Remove(lru.List.Back())
		}
		lru.List.PushFront(Pair{key: key, value: value})
		lru.Cache[key] = lru.List.Front()
	}
}
